#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x), next(nullptr){}
};

class Solution{
    public:
    ListNode* ans1(ListNode* l1, ListNode* l2){
        ListNode* head = nullptr;
        ListNode* tail = nullptr;
        int up = 0;
        int n1, n2;
        while(l1 || l2){
            if(l1){
                n1 = l1->val;
            }else{
                n1 = 0;
            }
            if(l2){
                n2 = l2->val;
            }else{
                n2 = 0;
            }
            int temp = n1 + n2 + up;

            if(!head){
                head = tail = new ListNode(temp % 10);
            }else{
                tail->next = new ListNode(temp % 10);
                tail = tail->next;
            }
            up = temp / 10;
            if(l1){
                l1 = l1->next;
            }
            if(l2){
                l2 = l2->next;
            }
        }
        if(up > 0){
            tail->next = new ListNode(up);
        }
        return head;
    }

};

void test1(){
    ListNode* l1_head1 = new ListNode(2);
    ListNode* l1_head2 = new ListNode(4);
    ListNode* l1_head3 = new ListNode(3);

    l1_head1->next = l1_head2;
    l1_head2->next = l1_head3;
    l1_head3->next = NULL;

    ListNode* l2_head1 = new ListNode(5);
    ListNode* l2_head2 = new ListNode(6);
    ListNode* l2_head3 = new ListNode(4);

    l2_head1->next = l2_head2;
    l2_head2->next = l2_head3;
    l2_head3->next = NULL;
    
    Solution s;
    cout << "-----------test1--------------" << endl;
    ListNode* ret = s.ans1(l1_head1, l2_head1);
    while(ret != nullptr){
        cout << ret->val << endl;
        ret = ret->next;
    }
}

void test2(){
    ListNode* l1 = nullptr;
    ListNode* l1_next = nullptr;
    vector<int> num1 = {9,9,9,9,9,9,9};
    for(int i = 0; i != num1.size(); i++){
        if(!l1){
            l1 = l1_next = new ListNode(num1[i]);
        }else{
            l1_next->next = new ListNode(num1[i]);
            l1_next = l1_next->next;
        }
    }

    ListNode* l2 = nullptr;
    ListNode* l2_next = nullptr;
    vector<int> num2 = {9,9,9,9};
    for(int i = 0; i != num2.size(); i++){
        if(!l2){
            l2 = l2_next = new ListNode(num2[i]);
        }else{
            l2_next->next = new ListNode(num2[i]);
            l2_next = l2_next->next;
        }
    }

    Solution s;
    cout << "-----------test2--------------" << endl;
    ListNode* ret = s.ans1(l1, l2);
    while(ret != nullptr){
        cout << ret->val << endl;
        ret = ret->next;
    }
}


int main(void){
    test1();
    test2();

    return 0;
}